# 源自：https://blog.csdn.net/CQZHOUZR/article/details/121862680

import copy

from 阵势 import *

上,下,左,右=0,2,3,1

class node:
    def __init__(self):
        self.战场= copy.deepcopy(场地初始状态)
        self.对局=[]
        self.当前移动=0
        self.移动队列=[]  #存储该棋局所有的可能下一步
             
    def 对称(self): #计算棋局的左右对称的棋局
        t=copy.deepcopy(self.战场)
        for i in range(1,6):
            for j in (1,3):
                t[i][j],t[i][5-j]=t[i][5-j],t[i][j]
        return t
        
    def print_board(self):
        for i in self.战场:
            print(i)


    def 更新棋子占据位置(self,棋子):        
        x=棋子.坐标[0]+1
        y=棋子.坐标[1]+1        
        if 棋子.形状==3:
            self.战场[x][y]=棋子.形状
            self.战场[x+1][y]=棋子.形状
        elif 棋子.形状==4:
            self.战场[x][y]=棋子.形状
            self.战场[x+1][y]=棋子.形状
            self.战场[x][y+1]=棋子.形状
            self.战场[x+1][y+1]=棋子.形状
        elif 棋子.形状==2:
            self.战场[x][y]=棋子.形状
            self.战场[x][y+1]=棋子.形状
        else: #卒
            self.战场[x][y]=棋子.形状
 
    def 更新棋盘占据位置(self):
        self.战场 = copy.deepcopy(场地初始状态)
        for x in self.对局:
            self.更新棋子占据位置(x)        
 
    def 更新棋子移动性(self,棋子):        
        x=棋子.坐标[0]+1
        y=棋子.坐标[1]+1
        棋子.可走方向=[0,0,0,0]
        if 棋子.形状==3:
            if self.战场[x][y-1]==0 and self.战场[x+1][y-1]==0:
                棋子.可走方向[左]=1  
            if self.战场[x-1][y]==0:
                棋子.可走方向[上]=1   
            if self.战场[x+2][y]==0:
                棋子.可走方向[下]=1   
            if self.战场[x][y+1]==0 and self.战场[x+1][y+1]==0:
                棋子.可走方向[右]=1   
        elif 棋子.形状==4:
            if self.战场[x][y-1]==0 and self.战场[x+1][y-1]==0:
                棋子.可走方向[左]=1  
            if self.战场[x-1][y]==0 and self.战场[x-1][y+1]==0:
                棋子.可走方向[上]=1   
            if self.战场[x+2][y]==0 and self.战场[x+2][y+1]==0:
                棋子.可走方向[下]=1   
            if self.战场[x][y+2]==0 and self.战场[x+1][y+2]==0:
                棋子.可走方向[右]=1   
        elif 棋子.形状==2:
            if self.战场[x][y-1]==0 :
                棋子.可走方向[左]=1  
            if self.战场[x-1][y]==0 and self.战场[x-1][y+1]==0:
                棋子.可走方向[上]=1   
            if self.战场[x+1][y]==0 and self.战场[x+1][y+1]==0:
                棋子.可走方向[下]=1   
            if self.战场[x][y+2]==0:
                棋子.可走方向[右]=1
        else: #卒
            if self.战场[x][y-1]==0 :
                棋子.可走方向[左]=1  
            if self.战场[x-1][y]==0 :
                棋子.可走方向[上]=1   
            if self.战场[x+1][y]==0:
                棋子.可走方向[下]=1   
            if self.战场[x][y+1]==0:
                棋子.可走方向[右]=1   
        棋子.可动 = sum(棋子.可走方向) > 0

    def 更新棋盘移动性(self):
        for x in self.对局:
            self.更新棋子移动性(x)

    def 生成移动队列(self):
        self.移动队列=[]
        self.当前移动=0
        for x in self.对局:
            if x.可动:
                for i in range(4):
                    if x.可走方向[i]==1: #1表示可移动，则将[移动方向,棋子]加入移动队列
                        self.移动队列.append([i,x.名称])      
               
    def 移动棋子(self,x):        
        for i in self.对局:
            if i.名称!=x[1]:
                continue
            if x[0]==上:
                i.坐标[0]-=1  
            elif x[0]==下:
                i.坐标[0]+=1  
            elif x[0]==左:
                i.坐标[1]-=1  
            elif x[0]==右:
                i.坐标[1]+=1  

    def 成功(self):
        for i in self.对局:
            if i.名称=="曹操":
                if i.坐标[0]==3 and i.坐标[1]==1:                
                    return True
                if i.坐标[0]==2 and i.坐标[1]==1:
                    if self.战场[4+1][1+1]==0 and self.战场[4+1][2+1]==0:
                        return True
                if i.坐标[0]==3 and i.坐标[1]==0:
                    if self.战场[3+1][2+1]==0 and self.战场[4+1][2+1]==0:
                        return True
                if i.坐标[0]==3 and i.坐标[1]==2:
                    if self.战场[3+1][1+1]==0 and self.战场[4+1][1+1]==0:
                        return True
        return False

棋局堆栈=[]       
根节点=node()

根节点.对局.append(曹操)
根节点.对局.append(马超)
根节点.对局.append(黄忠)
根节点.对局.append(张飞)
根节点.对局.append(赵云)
根节点.对局.append(关羽)
根节点.对局.append(卒1)
根节点.对局.append(卒2)
根节点.对局.append(卒3)
根节点.对局.append(卒4)
 
#初始化        
根节点.更新棋盘占据位置()
根节点.更新棋盘移动性()
根节点.生成移动队列()

记录形势(根节点.战场)
棋局堆栈.insert(0,根节点)
    
while True:
    while True:        
        if 棋局堆栈[0].当前移动>=len(棋局堆栈[0].移动队列):
             棋局堆栈.pop(0)  #当前棋局已无路可走，出栈               
             continue        
        节点=copy.deepcopy(棋局堆栈[0])
        节点.移动棋子(节点.移动队列[节点.当前移动])
        棋局堆栈[0].当前移动+=1    
        节点.更新棋盘占据位置()
        if 已见形势(节点.战场) or 已见形势(节点.对称()):            
            continue            
        else:        
            break   
    节点.更新棋盘移动性()
    节点.生成移动队列()
    记录形势(节点.战场)
    if 节点.成功():
        节点.print_board()  
        for k in range(len(棋局堆栈)):            
            #棋局堆栈[k].print_board()            
            print("移动棋子:{}".format(棋局堆栈[k].移动队列[棋局堆栈[k].当前移动-1]))            
            print("-----------------------")
        print("成功!步数：{}".format(len(棋局堆栈)))      
        break
    else:
        棋局堆栈.insert(0,节点)    
 
 